﻿#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;
using System.Collections;
using System.Collections.Generic;
using AbstractClass.Extensions;
using AbstractClass.Linq;

namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents a specialized tree-based data structure that satisfies the heap property:
    /// <para/>
    /// if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the
    /// greatest key is always in the root node, and so such a heap is sometimes called a
    /// max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the
    /// root node, which results in a min-heap.)
    /// </summary>
    /// <typeparam name="T">The type of the data in the heap.</typeparam>
    public sealed class Heap<T> : IAlgorithmAwareCollection<T, Heap<T>>
    {
        private readonly IComparer<T> _comparer = Comparer<T>.Default;
        private readonly List<T> _heap;


        /// <summary>
        /// Initializes a new instance of the <see cref="Heap&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="heapType">Type of the heap.</param>
        public Heap(HeapType heapType)
            : this(heapType, Comparer<T>.Default)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="Heap&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="heapType">Type of the heap viz. Max-heap / Min-heap.</param>
        /// <param name="comparer">The <see cref="IComparer&lt;T&gt;"/> implementation to use to sort
        /// the data in the heap.</param>
        public Heap(HeapType heapType, IComparer<T> comparer)
            : this(null, heapType, comparer)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="Heap&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="collection">The collection from which elements will be copied to the heap.</param>
        /// <param name="heapType">Type of the heap viz. Max-heap / Min-heap.</param>
        /// <param name="comparer">The <see cref="IComparer&lt;T&gt;"/> implementation to use to sort
        /// the data in the heap.</param>
        public Heap(IEnumerable<T> collection, HeapType heapType, IComparer<T> comparer)
        {
            _heap = !collection.IsNullOrEmpty() ? new List<T>(collection) {default(T)} : new List<T> {default(T)};
            _comparer = heapType != HeapType.Minimum ? comparer.GetReverse() : comparer;
            HeapType = heapType;
            Count = 0;
        }

        /// <summary>
        /// Gets the root element of the heap.
        /// </summary>
        /// <value>The root element.</value>
        /// <exception cref="InvalidOperationException">Heap is empty.</exception>
        public T Root
        {
            get
            {
                if (_heap.Count > 1)
                    return _heap[1];
                throw new InvalidOperationException(LanguageResource.EmptyHeapNoRoot);
            }
        }

        /// <summary>
        /// Gets or sets the type of the heap.
        /// </summary>
        /// <value>The type of the heap.</value>
        public HeapType HeapType { get; private set; }

        #region IAlgorithmAwareCollection<T,Heap<T>> Members

        /// <summary>
        /// Gets the total number of elements in the <see cref="Heap&lt;T&gt;"/>.
        /// </summary>
        public int Count { get; private set; }

        /// <summary>
        /// Adds an item into the <see cref="Heap&lt;T&gt;"/>.
        /// </summary>
        /// <param name="item">The item to add into the <see cref="Heap&lt;T&gt;"/>.</param>
        public void Add(T item)
        {
            _heap.Add(default(T));
            int counter = _heap.Count - 1;
            while ((counter > 1) && (_comparer.Compare(_heap[counter / 2], item) > 0))
            {
                _heap[counter] = _heap[counter / 2];
                counter = counter / 2;
            }
            _heap[counter] = item;
            Count++;
        }

        /// <summary>
        /// Clears this instance by removing all items from it.
        /// </summary>
        public void Clear()
        {
            _heap.RemoveRange(1, _heap.Count - 1);
            Count = 0;
        }

        /// <summary>
        /// Determines whether <paramref name="item"/> is in the <see cref="Heap&lt;T&gt;"/>.
        /// </summary>
        /// <param name="item">The data to find in the <see cref="Heap&lt;T&gt;"/>.</param>
        /// <returns>
        /// <c>true</c> if found; otherwise, <c>false</c>.
        /// </returns>
        public bool Contains(T item)
        {
            return _heap.Contains(item);
        }

        /// <summary>
        /// Copies the elements of the <see cref="Heap&lt;T&gt;"/> to an array of type
        /// <typeparamref name="T"/>, starting at the specified array index.
        /// </summary>
        /// <param name="array">The one-dimensional array of type T that is the destination of
        /// the elements copied from the <see cref="Heap&lt;T&gt;"/>. The array must have zero-based indexing.
        ///	 </param>
        /// <param name="arrayIndex">The zero-based index in array at which copying begins.</param>
        /// <remarks>The nodes are fetched in In-Order fashion.</remarks>
        public void CopyTo(T[] array, int arrayIndex)
        {
            for (int i = 1; i < _heap.Count; i++)
            {
                array[arrayIndex++] = _heap[i];
            }
        }

        /// <summary>
        ///   Gets a value indicating whether the <see cref="Heap&lt;T&gt;"/> is read-only.
        /// </summary>
        /// <returns>
        ///   true if the <see cref="Heap&lt;T&gt;"/> is read-only; otherwise, false.
        /// </returns>
        public bool IsReadOnly
        {
            get { return false; }
        }

        bool ICollection<T>.Remove(T item)
        {
            Swap(1, Count);
            Count--;
            if (Count != 0)
            {
                PushDown(1);
                return true;
            }
            return false;
        }

        /// <summary>
        ///   Returns an enumerator that iterates through the collection.
        /// </summary>
        /// <returns>
        ///   A <see cref = "IEnumerator&lt;T&gt;" /> that can be used to iterate through the collection.
        /// </returns>
        public IEnumerator<T> GetEnumerator()
        {
            for (int i = 1; i < _heap.Count; i++)
            {
                yield return _heap[i];
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        /// <summary>
        /// Removes the root item from the heap.
        /// </summary>
        /// <returns>The removed element.</returns>
        public T RemoveItem()
        {
            T root = Root;
            Swap(1, Count);
            Count--;
            if (Count != 0)
                PushDown(1);
            return root;
        }

        /// <summary>
        /// Merges <paramref name="heap"/> with this instance.
        /// </summary>
        /// <param name="heap">The heap to merge with the current instance.</param>
        /// <exception cref="ArgumentException">Specified heap is of different <see cref="HeapType"/> than this.</exception>
        public void Merge(Heap<T> heap)
        {
            if (HeapType == heap.HeapType)
            {
                heap.Process(Add);
            }
            else
                throw new ArgumentException(LanguageResource.HeapTypeMismatch);
        }

        private static int GetLeftChild(int pos)
        {
            return 2 * pos;
        }

        private bool IsLeaf(int pos)
        {
            return ((pos > Count / 2) && (pos <= Count));
        }

        private void Swap(int pos1, int pos2)
        {
            T tmp = _heap[pos1];
            _heap[pos1] = _heap[pos2];
            _heap[pos2] = tmp;
        }

        private void PushDown(int position)
        {
            while (!IsLeaf(position))
            {
                int smallestchild = GetLeftChild(position);
                if ((smallestchild < Count) && _comparer.Compare(_heap[smallestchild], _heap[smallestchild + 1]) > 0)
                    smallestchild = smallestchild + 1;
                if (_comparer.Compare(_heap[position], _heap[smallestchild]) <= 0) return;
                Swap(position, smallestchild);
                position = smallestchild;
            }
        }

        #region Implementation of IAlgorithmAware<out Heap<T>>

        /// <summary>
        /// Executes the <paramref name="algorithm"/> on the heap.
        /// </summary>
        /// <typeparam name="TResult">The type of the result.</typeparam>
        /// <param name="algorithm">The algorithm to run on a heap.</param>
        /// <returns>Result of execution of the algorithm on the heap.</returns>
        public TResult ExecuteAlgorithm<TResult>(IAlgorithm<Heap<T>, TResult> algorithm)
        {
            algorithm.ThrowIfNull("algorithm");
            return algorithm.Run(this);
        }

        #endregion
    }
}